package com.ryujung.linked_list.leetCode_142;

import com.ryujung.linked_list.node.ListNode;

class Solution {

    /**
     * 思路：
     * 使用快慢指针，设法让快慢指针在出现环路的位置相遇
     * 步骤：
     * 1.首先通过快慢指针判断是否存在环路，无环路直接返回
     * 2.存在环路，则从相遇的节点开始遍历，获取环的长度len
     * 3.使用双指针，间距len个节点，从头遍历链表，
     * 这样当第一指针到达尾部，第二指针就到达尾部连接的节点
     */
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        ListNode meetNode = null;

        while (fast != null && fast.next != null && slow != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) {
                meetNode = fast;
                break;
            }
        }

        if (meetNode == null) return null;

        // 存在环，计算环的长度
        int roundLength = 1;
        while (slow.next != meetNode) {
            slow = slow.next;
            roundLength++;
        }

        // 使用双指针从头遍历链表
        ListNode first = head;
        ListNode second = head;
        for (int i = 0; i < roundLength; i++) {
            first = first.next;
        }
        // 两指针再次相遇的地方就是环路产生的节点
        while (first != second) {
            first = first.next;
            second = second.next;
        }
        return first;
    }
    // 时间复杂度：O(n)
    // 空间复杂度：O(1)
}